This invention relates in general to the field of computer graphics, and in particular to the processing of images to reduce the aliasing effects of pixel sampling.
Computers are known to include processors, memory, and display devices. With ever increasing advances in computer applications, the need for improved display quality continues. Computer displays must be able to present high resolution, high quality images at rapid refresh rates. Video graphic circuits and systems must be able to provide the data for such displays efficiently and effectively, often within highly competitive cost and compatibility constraints.
Computer displays, and other high resolution display devices such as high definition televisions (HDTV), projectors, printers, plotters, and the like, present an image to the viewer as an array of individual picture elements, or pixels. The individual pixels are each given a specific characteristic, such as the color of the image at the particular pixel""s location. The pixels are closely spaced, and the viewer""s visual system performs a filtering of the individual pixel color values to form a composite image. If the partitioning of the image into individual pixel elements is performed properly, and the pixels are close enough together, the viewer perceives the displayed array of pixels as a virtually continuous image. Despite the viewer""s visual filtering, the viewer remains sensitive to aberrations in the image, and video graphic systems must be designed to minimize these aberrations.
If the image is insufficiently sampled, visual aberrations will be produced. A highly detailed image with numerous changes within a short span of points will have a high frequency of change; a blank image has a zero frequency of change. If the frequency of pixel value sampling is less than twice the image""s frequency of change, aliasing will occur, and visual aberrations will be introduced into the image. That is, not only will the displayed image not contain the detail of the original image, but additional components, not contained in the original image, will be added. In addition to being visually disturbing, the introduction of sampling artifacts, not contained in the original image, can be particularly problematic if the display is used for mapping or medical applications (x-rays, MRI scans, etc.)
Aliasing will occur whenever the sampling rate is less than twice the highest frequency change in the image. Traditionally, the pixel sampling rate is equal to the pixel spatial frequency. That is, if there are 640 pixels per line of display, a full screen image will be sampled at 640 points across its horizontal dimension. If the image being sampled has a highest frequency that is greater than half the pixel sampling rate, then either the image highest frequency must be reduced, or the pixel sampling rate must be increased. These techniques, of reducing the image frequency, or increasing the pixel sampling frequency, are termed xe2x80x9canti-aliasingxe2x80x9d techniques. Filtering the image to remove the high frequency components before the image is sampled for display reduces the image highest frequency. Increasing the number of pixels per line of display, i.e. increasing the display resolution, increases the pixel sampling rate. High resolution displays, however, are significantly more costly than lower resolution displays. A preferred alternative for increasing the number of pixel samples per line is to obtain multiple samples of the image within each pixel; that is, by super-sampling at a subpixel resolution. The value presented to the display as the pixel value corresponding to the image will be the average of the multiple sample values obtained within each pixel.
To effect super-sampling, multiple points within each pixel are selected as sampling points, and the image is sampled at each of these points. To display the pixel, a single value is assigned, based on a composite of the multiple super-samples. Typically, the single value determined for a pixel will be the average of the values assigned at each super-sampled point within the pixel, although other means of forming a representative statistic may be employed. The averaging of the super-samples has the effect of reducing the high-frequency changes in the image. Consider, for example, a pixel that lies on the border of two objects, such that some of the super-sampled values contain the first object""s value, and some contain the other object""s value. The pixel will be assigned an average value of the sampled values, producing a smoothing, or blending at the transition between the two objects, thereby effectively reducing the high frequency components of the image.
The super-samples are conventionally uniformly distributed about the pixel area, thereby assuring that the average is an unbiased estimate of the object values within the pixel area. To obtain 4 super-samples per pixel, the pixel is divided into a 2xc3x972 grid, forming 4 subpixels, and each super-sample value is obtained at the center of each subpixel. Similarly, to obtain 16 super-samples per pixel, the pixel is divided into a 4xc3x974 grid, forming 16 subpixels. FIGS. 1A-1E illustrate, respectively, subpixel partitionings for providing for 1, 4, 8, 16, 32, and 64 super-samples per pixel in a conventional super-sampling process. The number of subpixels per pixel is termed the subpixel resolution. Each pixel is sampled at each of the subpixels identified by dots in FIGS. 1A-1E. Because the dots are uniformly distributed, a uniform sampling frequency is assured.
Because super-sampling effectively increases the sampling frequency, super-sampling provides an effective anti-aliasing solution, but it requires significant additional processing and memory resources. Consider, for example, a common 640xc3x97480 pixel display, wherein each pixel is super-sampled based on a 4xc3x974 subpixel resolution (FIG. 1C). For each of the 307,200 (640*480) pixels, 16 sample values will be determined, each requiring data access and computation time and resources. In three-dimensional graphics, because one object may block another from view, it often cannot be determined which objects are visible until all the objects are processed, and therefore, in general, the 16 sample values for each of the 307,200 pixels must be stored. The composite value for each pixel is determined from these stored values after all the objects in the image are processed, requiring a substantial number (16 * 307,200) of data accesses to form the composite image. With an ever increasing need to improve video graphic processing speed while at the same time reducing costs, the significant amount of processing and storage required for subpixel sampling places a limit on the practical application of this anti-aliasing technique.
Therefore, a need exists for an anti-aliasing technique that provides the anti-aliasing qualities of a high super-sampling frequency, but does not incur a correspondingly high computation and memory resource requirement increase. A need also exists for a technique for storing super-samples that minimizes data access time.